<!DOCTYPE html>
<html lang=en-US class="noScroll">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge">

        <title>Equivalence Relation</title>

        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/fonts.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/links.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/search.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/mathJax.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/darkMode.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/variables.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/noProperty.css">

        <script src="https://cdn.jsdelivr.net/npm/fuse.js/dist/fuse.js"></script>

        <script src="https://zhaoshenzhai.github.io/mathwiki/js/input.js" type="module"></script>
        <script src="https://zhaoshenzhai.github.io/mathwiki/js/search.js" type="module"></script>
        <script src="https://zhaoshenzhai.github.io/mathwiki/js/mathJax.js" type="module" async></script>
        <script src="https://zhaoshenzhai.github.io/mathwiki/js/darkMode.js" type="module"></script>

        <div style="display:none;" id="preamble"></div>
    </head>

    <body class="listenDark">
        
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/metaLinks.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/metaTOC.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/preview.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/expand.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/side.js" type="module"></script>

    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/ctrlButtons.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/collapsible.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/metadata.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/preview.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/single.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/env.css">

    <div id="mainPage">
        <button id="toggleDark" onclick="toggleDark(document, false, true, true);" class="ctrlButton noSelect inPreview">
            <img id="toggleDarkIcon" src="https://zhaoshenzhai.github.io/mathwiki/css/fa/sun.svg">
        </button>
        <button id="toggleSide" onclick="toggleSide(false);" class="ctrlButton noSelect inPreview">
            <img id="toggleSideIcon" src="https://zhaoshenzhai.github.io/mathwiki/css/fa/sun.svg">
        </button>
        <div id="content" class="left noScroll">
            
                <h1 id="title" titleSize="">
                    Equivalence Relation
                </h1>
            
            <h1 id="motivation--definition">Motivation &amp; Definition</h1>
<p>Oftentimes, we wish to regard two objects as ‘being the same’ (for instance, two sets are ‘the same’ if they have the same <a href=https://zhaoshenzhai.github.io/mathwiki/cardinality.md class="internalLink references ghostLink" title="cardinality" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/cardinality.md&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/cardinality.md&#34;, &#34;nopPage&#34;);">cardinality</a>), despite them not being <em>equal</em>. The concept of an <em>equivalence relation</em> can be thought of as a generalization of equality.</p>
<div class="env envDef" id=""><img class="icon noSelect listenDark" src="https://zhaoshenzhai.github.io/mathwiki/css/fa/definition.svg"><b class="envTitle">Definition. </b><p>Let $X$ be a set. An <em>equivalence relation</em> on $X$ is a (binary) relation $E\subseteq X^2$ subject to the following conditions.</p>
<ol>
<li><span style="color:gray">(Reflexive).</span> For all $x\in X$, we have $(x,x)\in E$.</li>
<li><span style="color:gray">(Symmetric).</span> For all $x,y\in X$, we have $(x,y)\in E$ iff $(y,x)\in E$.</li>
<li><span style="color:gray">(Transitive).</span> For all $x,y,z\in X$, if both $(x,y),(y,z)\in E$, then $(x,z)\in E$.</li>
</ol>
<p>We usually write $xEy$ for $(x,y)\in E$ instead.</p>
</div>

<p>For every $x\in X$, we have its <em>equivalence class</em> $[x]_E\coloneqq\l\{y\in X\st xEy\r\}$. More generally, the <em>saturation</em> of $A\subseteq X$ is the union $[A]_E\coloneqq\bigcup_{x\in A}[x]_E$. Subsets $I\subseteq X$ that are the union of equivalence classes $-$ or equivalently, $I=[I]_E$ $-$ are said to be <em>$E$-invariant</em>.</p>
<h2 id="partitions">Partitions</h2>
<p>Equivalence relations on $X$ are in correspondence with <em>partitions</em> of $X$, which are families $\mc{P}\subseteq2^X$ of non-empty disjoint subsets of $X$ with $\bigsqcup\mc{P}=X$.</p>
<br>
<p>  Indeed, if $E$ is an equivalence relation on $X$, then $\mc{P}_E\coloneqq\l\{[x]_E\subseteq X\st x\in X\r\}$ is a partition of $X$. Conversely, given a partition $\mc{P}$ on $X$, the relation $E$, defined by $xEy$ iff $x,y\in P$ for some $P\in\mc{P}$, is an equivalence.</p>
<h2 id="hahahugoshortcode19s2hbhb"><a href=https://zhaoshenzhai.github.io/mathwiki/quotient_set.md class="internalLink constructions" title="Quotient Set" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/quotient_set.md&#34;, {&#34;Date&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Quotient Set&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/quotient_set&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Quotient Set&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/quotient_set&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/quotient_set.md&#34;, {&#34;Date&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-06-11T21:27:54-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Quotient Set&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/quotient_set&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">Quotient Set</a></h2>
<p>Given an equivalence $E$ on $X$, we would like to construct some set $X/E$ where ‘$E$ becomes equality’. Moreover, this construction should be ‘the most efficient’ way of doing so, in the sense of a suitable <a href=https://zhaoshenzhai.github.io/mathwiki/universal_constructions.md class="internalLink references" title="Universal Constructions" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/universal_constructions.md&#34;, {&#34;Date&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Universal Constructions&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/universal_constructions&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Universal Constructions&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/universal_constructions&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/universal_constructions.md&#34;, {&#34;Date&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-05-29T17:38:25-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Universal Constructions&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/universal_constructions&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">universal property</a>.</p>
<br>
<p>  This can be done by setting $X/E\coloneqq\mc{P}_E$, so that $xEy$ iff $[x]_E=[y]_E$, and we call $X/E$ the <em>quotient set of $X$ by $E$</em>.</p>
<h1 id="examples-and-generalizations">Examples and Generalizations</h1>
<h2 id="hahahugoshortcode19s4hbhb"><a href=https://zhaoshenzhai.github.io/mathwiki/groupoid.md class="internalLink generalizations ghostLink" title="Groupoid" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/groupoid.md&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/groupoid.md&#34;, &#34;nopPage&#34;);">Groupoid</a></h2>
<h2 id="hahahugoshortcode19s5hbhb"><a href=https://zhaoshenzhai.github.io/mathwiki/congruence_relation.md class="internalLink types ghostLink" title="Congruence Relation" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/congruence_relation.md&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/congruence_relation.md&#34;, &#34;nopPage&#34;);">Congruence Relation</a></h2>
<h1 id="classification-problems-and-dynamics">Classification Problems and Dynamics</h1>


            <div class="bottomSpace">&nbsp;</div>
        </div>

        <div id="side" class="inPreview">
            <div id="metadata" class="right noScroll">
                June 18, 2024 | Zhaoshen Zhai

                <div>References:
                     None 
                </div>
                <div>Tags:
                    
                        <div class="metaButton metaTag listenDark">#In_Progress</div>
                    
                </div>
                <br>

                <div>Table of Contents:
                    <button class="metaButton listenDark" onclick="showMetaTOC();">Show</button>
                    <button class="metaButton listenDark" onclick="hideMetaTOC();">Hide</button>
                    <div id="metaTOC"></div>
                </div>
                <div>Links:
                    <button class="metaButton listenDark" onclick="expandMetaLinks();">Expand</button>
                    <button class="metaButton listenDark" onclick="collapseMetaLinks();">Collapse</button>
                    <div id="metaLinks"></div>
                </div>

                <div class="bottomSpace">&nbsp;</div>
            </div>
            <div id="previewContainer">
                <button id="resetSide" onclick="resetSide();" class="ctrlButton noSelect" style="display: none;">
                    <img src="https://zhaoshenzhai.github.io/mathwiki/css/fa/close.svg">
                </button>
            </div>
        </div>
    </div>


        <div id="searchBox" style="display: none;">
            <input id="searchBar" placeholder="Search for a note..." onkeydown="search(event);">
            <ul id="searchList" onclick="searchOpen(getCtrlKeyDown());">
                <li id="searchItem0" onmouseover="searchItemActive(0)"></li>
                <li id="searchItem1" onmouseover="searchItemActive(1)"></li>
                <li id="searchItem2" onmouseover="searchItemActive(2)"></li>
                <li id="searchItem3" onmouseover="searchItemActive(3)"></li>
                <li id="searchItem4" onmouseover="searchItemActive(4)"></li>
                <li id="searchItem5" onmouseover="searchItemActive(5)"></li>
                <li id="searchItem6" onmouseover="searchItemActive(6)"></li>
                <li id="searchItem7" onmouseover="searchItemActive(7)"></li>
                <li id="searchItem8" onmouseover="searchItemActive(8)"></li>
                <li id="searchItem9" onmouseover="searchItemActive(9)"></li>
            </ul>
        </div>
    </body>
</html>
